The public key cryptosystem realizes cryptographic communication decryptable only by a transmission party by transmitting data encrypted with a transmission party's public key so that it can be decrypted by the transmission party with a secret key paired with the public key.
Conventionally, in order to guarantee that a public key belongs to a transmission party, verification is performed on a public key certificate issued by a public key certification authority.
Moreover, in order to guarantee the correspondence between a public key and its owner even if there is no infrastructure like the public key certification authority, there has been proposed the ID-based cryptographic communication system using an identification name (ID), such as a transmission party's name, a name, and an equipment number, as the public key.
For guaranteeing the security of a public key cryptosystem, proving is performed by letting the security of a public key cryptosystem reduce to the difficulty of solving a mathematical problem.
That is, assuming that there is an attacker who can stochastically break the cipher, when an algorithm exists that can solve a mathematical problem by utilizing the attacker, it can be said that such cryptographic system is reduced to the mathematical problem.
In the proving, what is important is whether the reduced mathematical problem is good or bad, the reduction rate is good or bad, and the model is good or bad.
The goodness or badness of the reduced mathematical problem indicates the difficulty of solving the problem. It can be said that the public key cryptosystem reducible to a problem being difficult to solve has high security by that much.
The goodness or badness of the reduction rate indicates a relation between the resources (time, memory, etc.) exploited by the attacker in order to break a cipher and the resources exploited in order to solve a mathematical problem by utilizing the attacker. If there is not so much difference between the resources required for breaking the cipher and the resources required for solving the mathematical problem, it can be said that the reduction rate is good. In this case, if it is possible to break the cipher, it means it is possible to solve the mathematical problem. Contrapositively, if it is difficult to solve the mathematical problem, to break the cipher is as difficult as the solving. On the other hand, when the reduction rate is bad, that is, when the resources required for solving the mathematical problem are very large in comparison with the resources required for breaking the cipher, even if it is difficult to solve the mathematical problem, to break the cipher is not necessarily as difficult as the solving.
The goodness or badness of the model indicates whether the model being a premise of the proving is practical or not. For example, a model without using a random oracle is better than a model assuming a random oracle.    [Patent Literature 1] International Publication No. 2005-050908    [Non-patent Literature 1] Ryuichi SAKAI, Kiyoshi OHGISHI, and Masao KASAHARA, “Cryptosystems based on Pairing over Elliptic Curve” Symposium on Cryptography and Information Security (SCIS 2001), 2001    [Non-patent Literature 2] Dan Boneh, and Matt Franklin, “Identity-Based Encryption from the Weil Pairing”, Crypto 2001, LNCS 2139, pp. 213-229, 2001    [Non-patent Literature 3] Xavier Boyen, “The BB1 Identity-Based Cryptosystem: A Standard for Encryption and Key Encapsulation”, Submissions for IEEE P1363.3, 2006 (http://grouper.ieee.org/groups/1363/IBC/submissions/index.html)    [Non-patent Literature 4] Craig Gentry, “Practical Identity-Based Encryption Without Random Oracles”, Eurocrypt 2006, LNCS 4004, pp. 445-464, 2006    [Non-patent Literature 5] Jung Hee Cheon, “Security Analysis of the Strong Diffie-Hellman Problem”, Eurocrypt 2006, pp. 1-13, 2006    [Non-patent Literature 6] Mihir Bellare, Alexandra Boldyreva, and Silvio Micali, “Public-key Encryption in a Multi-User Setting: Security Proofs and Improvements”, Eurocrypt 2000, LNCS1807, 2000 (http://www-cse.ucsd.edu/users/mihir/crypto-research-papers.html)    [Non-patent Literature 7] Mihir Bellare, Alexandra Boldyreva, and Jessica Staddon, “Multi-Recipient Encryption Schemes: Security Notions and Randomness Re-Use”, PKC 2003, LNCS 2567, 2003 (http://www-cse.used.edu/users.mihir/crypto-research-papers.html)    [Non-patent Literature 8] Ronald Cramer, and Victor Shoup, “Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack”, SIAM. J. Comput, vol. 33, 2003    [Non-patent Literature 9] Dan Boneh, and Xavier Boyen, “Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles”, Eurocrypt 2004, LNCS 3027, pp. 223-238, 2004 (http://crypto.stanford.edu/˜dabo/)    [Non-patent Literature 10] Brent Waters, “Efficient Identity-Based Encryption Without Random Oracles”, Eurocrypt 2005 (http://www.csl.sri.com/users/bwaters/publications/publications.html)    [Non-patent Literature 11] David Naccache, “Secure and Practical Identity-Based Encryption” (http://eprint.iacr.org/2005/369)    [Non-patent Literature 12] Sanjit Chatterjee, and Palash Sarkar, “Trading Time for Space: Towards an Efficient IBE Scheme with Short(er) Public Parameters in the Standard Model”, ICISC 2005, LNCS 3935, pp. 424-440, 2006    [Non-patent Literature 13] N. P. Smart, “Efficient Key Encapsulation to Multiple Parties”, SCN 2004, LNCS 3352, pp. 208-219, 2005    [Non-patent Literature 14] M. Barbosa, and P. Farshim, “Efficient Identity-Based Key Encapsulation to Multiple Parties”, Cryptography and Coding, 10th IMA Int. Cof. 2005, LNCS 3796, Springer Verlog, pp. 428-441, 2005    [Non-patent Literature 15] Joonsang Baek, Reihaneh Safavi-Naini, and Willy Susilo, “Efficient Multi-receiver Identity-Based Encryption and Its Application to Broadcast Encryption”, PKC 2005, LNCS 3386, pp. 380-397, 2005    [Non-patent Literature 16] Sanjit Chatterjee, and Palash Sarkar, “Generalization of the Selective-ID Security Model for HIBE Protocols”, PKC 2006, 2006    [Non-patent Literature 17] Sanjit Chatterjee, and Palash Sarkar, “Multi-receiver Identity-Based Key Encapsulation with ShortenedCiphertext”, Indocrypt2006, LNCS 4329, pp. 394-408, 2006    [Non-patent Literature 18] Xavier Boyen, Qixiang Mei, and Brent Waters, “Direct Chosen Ciphertext Security from Identity-Based Techniques” ACM-CC 2005, pp. 320-329, 2005